package basic.study.leetcode;

/**
 * @ClassName Hard312
 * @Description 戳气球
 * https://leetcode-cn.com/problems/burst-balloons/solution/zhe-ge-cai-pu-zi-ji-zai-jia-ye-neng-zuo-guan-jian-/
 * @Company inspur
 * @Author Kevin
 * @Date 2020/7/21 11:16
 * @Version 1.0
 */
public class Hard312 {
    class Solution {
        public int maxCoins(int[] nums) {
            int n = nums.length;
            // 创建一个辅助数组，并在首尾添加1，方便处理边界情况
            int[] temp = new int[n + 2];
            temp[0] = 1;
            temp[n+1] = 1;
            for (int i = 0; i < n; i++) {
                temp[i+1] = nums[i];
            }
            int[][] dp = new int[n+2][n+2];
            //len表示开区间长度,长度为3时候说明是最后的只剩一个气球，所以此时left right为0都可理解
            for (int len = 3; len<=n+2; len++) {
                // i 表示开区间左端点
                for (int i = 0; i <= n+2-len; i++) {
                    int res = 0;
                    // k 为开区间内的索引
                    for (int k = i+1; k < i+len-1; k++) {
                        int left = dp[i][k];
                        int right = dp[k][i+len-1];
                        res = Math.max(res, left + temp[i]*temp[k]*temp[i+len-1]+ right);
                    }
                    dp[i][i+len-1] = res;
                }
            }
            return dp[0][n+1];
        }
    }
}
